package acwing_04;
import java.io.*;
import java.util.*;
public class _867_分解质因数 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	public static void main(String[] args) throws IOException {
		// 质数=素数，因数=约数
		/* 质因数：
		    每个合数都可以写成几个质数相乘的形式。其中每个质数都是这个合数的因数，叫做质因数。
		    把一个合数用质因数相乘的形式表示出来，叫做分解质因数。
		*/
		int n = Integer.parseInt(br.readLine());
		
		while(n-- > 0) {
			divide(Integer.parseInt(br.readLine()));
			bw.newLine();
		}
		bw.flush();
	}
	public static void divide(int n) throws IOException {
		// 质数只会到 sqrt(n) 即 <= n / 1
		// 此外，有可能会有一个比sqrt(n)大的质数，只需要最后进行一次判断即可
		for(int i = 2; i <= n / i; i++) {
			// 从最小质数2开始取余，没有余数说明能被整除，则记录n被质数i整除能整除多少次
			// n % i == 0 能成立，说明i一定是质数
			// 因为n前面已经被质数2 3整除过了，前面的质因子已经被筛掉了
			// 假设如果i=4是合数，但是前面已经有2将4的倍数筛掉了，所以后续遇到的i能成立则一定是质数
			if(n % i == 0) {
				int s = 0;
				while(n % i == 0) {
					s++;
					n /= i;
				}
				bw.write(i + " " + s + "\n");
			}
		}
		// 如果n>1说明sqrt(n)前面的所有数都不是其质因子，则最后剩下的n就是最后最大的质因子
		if(n > 1) {
			bw.write(n + " " + 1  + "\n");
		}
		
	}
}
